import java.util.*;

class Demo {
    public static void main (String[] args) {
	//	runSort(new SelectionSort(), "Selection Sort");
	//	runSort(new InsertionSort(), "Insertion Sort");
	//	runSort(new MergeSort(), "Merge Sort");
	//	runSort(new QuickSortBad(), "Not So Good Quick Sort");
	//	runSort(new BubbleSort(), "Bubble Sort");
	//	runSort(new BetterBubbleSort(), "Better Bubble Sort");
		runSort(new QuickSort(), "Better Quick Sort");
    }

    static void runSort(Sort sorter, String sortName) {
	System.out.println("\n" + sortName + "\n");
	// Use 25600 for Selection, Insertion and Bubble
	// Use 409600 for Mergesort and Quick Sort (fast)
	// Use 6400 for Bad Quick Sort
	for (int SIZE = 100; SIZE <= 409600; SIZE *= 2) {
	    long start, end;
	    long elapsed1 = 0, elapsed2 = 0, elapsed3 = 0;
	    Comparable [ ] a = new Integer [ SIZE ];
	    
	    // sorted input
	    for( int i = 0; i < SIZE; i++ )
		a[ i ] = new Integer( i );
	    start = System.currentTimeMillis();
	    sorter.sort( a );
	    end = System.currentTimeMillis();
	    elapsed1 = end - start;
	    checkSort(a);

	    // reverse sorted input
	    for( int i = 0; i < SIZE; i++ )
		a[ i ] = new Integer( SIZE - i );
	    start = System.currentTimeMillis();
	    sorter.sort( a );
	    end = System.currentTimeMillis();
	    elapsed2 = end - start;
	    checkSort(a);

	    // random input
	    Random r = new Random();
	    for( int i = 0; i < SIZE; i++ )
		a[ i ] = new Integer( r.nextInt(SIZE) );
	    start = System.currentTimeMillis();
	    sorter.sort( a );
	    end = System.currentTimeMillis();
	    elapsed3 = end - start;
	    checkSort(a);

	    System.out.println("size: " + SIZE + 
			       "\tsorted: " + elapsed1 + 
			       "\treverse: " + elapsed2 + 
			       "\trandom: " + elapsed3);
	}
    }

    static void checkSort(Comparable[] array) {
	for( int i = 0; i < array.length-1; i++ ) {
	    if( array[i].compareTo(array[i+1]) > 0 ) {
		System.out.println( "array not sorted array["+i+"]=" +
				    array[i] + " array["+ (i+1) +
				    "]=" + array[i+1]);
	    }
	}
    }
}

interface Sort {
    public void sort( Comparable [ ] a );
}

class SelectionSort implements Sort {
    public void sort (Comparable[] a) {
	for (int i = 0; i < a.length-1; i++) {
	    int min = i;
	    for (int j = i+1; j < a.length; j++)
		if (a[j].compareTo(a[min]) < 0)
		    min = j;
	    Comparable tmp = a[min];
	    a[min] = a[i];
	    a[i] = tmp;
	}
    }
}

class InsertionSort implements Sort {
    public void sort( Comparable [ ] a ) {
        for( int p = 1; p < a.length; p++ ) {
            Comparable tmp = a[ p ];
            int j;
            for(j = p ; j > 0 && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
                a[ j ] = a[ j - 1 ];
            a[ j ] = tmp;
        }
    }
}

class BubbleSort implements Sort {
    public void sort (Comparable[] a) {
	for (int i = 0; i < a.length; i++) {
	    for (int j = 0; j < a.length-1; j++) {
		if (a[j].compareTo(a[j+1]) > 0) {
		    Comparable tmp = a[j];
		    a[j] = a[j+1];
		    a[j+1] = tmp;
		}
	    }
	}
    }
}

class BetterBubbleSort implements Sort {
    public void sort (Comparable[] a) {
	for (int i = 0; i < a.length; i++) {
	    boolean swap = false;
	    for (int j = 0; j < a.length-1-i; j++) {
		if (a[j].compareTo(a[j+1]) > 0) {
		    Comparable tmp = a[j];
		    a[j] = a[j+1];
		    a[j+1] = tmp;
		    swap = true;
		}
	    }
	    if (!swap) break;
	}
    }
}

class MergeSort implements Sort {
    public void sort (Comparable[] a) {
        mergeSort( a, 0, a.length - 1 );
    }
    static void mergeSort( Comparable [ ] a, int left, int right ) {
        if( left < right ) {
            int center = ( left + right ) / 2;
            mergeSort( a, left, center );
            mergeSort( a, center + 1, right );
            merge( a, left, center, right );
        }
    }
    static void merge( Comparable [ ] a, int left, int center, int right ) {
        int size = right - left + 1;
        Comparable [ ] tmp = new Comparable[ size ];
	int i = 0;
	int leftPos = left;
	int rightPos = center+1;
        while( leftPos <= center && rightPos <= right )
            if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
                tmp[ i++ ] = a[ leftPos++ ];
            else
                tmp[ i++ ] = a[ rightPos++ ];
        while( leftPos <= center )
            tmp[ i++ ] = a[ leftPos++ ];
        while( rightPos <= right )
            tmp[ i++ ] = a[ rightPos++ ];
        for( i = 0; i < size; i++ )
            a[ left+i ] = tmp[ i ];
    }
}

class QuickSort implements Sort {
    public void sort (Comparable[] a) {
        quicksort( a, 0, a.length - 1 );
    }
    private static final int CUTOFF = 10;
    public static final void swapReferences( Object [ ] a, int index1, int index2 )
    {
        Object tmp = a[ index1 ];
        a[ index1 ] = a[ index2 ];
        a[ index2 ] = tmp;
    }
    private static void quicksort( Comparable [ ] a, int low, int high )
    {
        if( low + CUTOFF > high )
            insertionSort( a, low, high );
        else
        {
                // Sort low, middle, high
            int middle = ( low + high ) / 2;
            if( a[ middle ].compareTo( a[ low ] ) < 0 )
                swapReferences( a, low, middle );
            if( a[ high ].compareTo( a[ low ] ) < 0 )
                swapReferences( a, low, high );
            if( a[ high ].compareTo( a[ middle ] ) < 0 )
                swapReferences( a, middle, high );

                // Place pivot at position high - 1
            swapReferences( a, middle, high - 1 );
            Comparable pivot = a[ high - 1 ];

                // Begin partitioning
            int i, j;
            for( i = low, j = high - 1; ; )
            {
                while( a[ ++i ].compareTo( pivot ) < 0 )
                    ;
                while( pivot.compareTo( a[ --j ] ) < 0 )
                    ;
                if( i >= j )
                    break;
                swapReferences( a, i, j );
            }

                // Restore pivot
            swapReferences( a, i, high - 1 );

            quicksort( a, low, i - 1 );    // Sort small elements
            quicksort( a, i + 1, high );   // Sort large elements
        }
    }
    private static void insertionSort( Comparable [ ] a, int low, int high )
    {
        for( int p = low + 1; p <= high; p++ )
        {
            Comparable tmp = a[ p ];
            int j;

            for( j = p; j > low && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
                a[ j ] = a[ j - 1 ];
            a[ j ] = tmp;
        }
    }
}

class QuickSortBad implements Sort {
    public void sort (Comparable[] a) {
        quicksortBad( a, 0, a.length - 1 );
    }
    static void quicksortBad( Comparable [ ] a, int low, int high ) {
        if( low < high ) {
	    	int pivot = partition(a, low, high);
            quicksortBad( a, low, pivot - 1 );
            quicksortBad( a, pivot + 1, high );
        }
    }
    static int partition (Comparable[] a, int low, int high) {
        Comparable pivot = a[low];
        int i = low;
	  int j = high+1;
	  while (i < j) {
	    do i++; while(i < j && a[ i ].compareTo( pivot ) < 0 );
	    do j--; while(i <= j && a[ j ].compareTo( pivot ) > 0 );
	    if (i < j) {
	      Comparable temp = a[i];
		a[i] = a[j];
		a[j] = temp;
            }
	}
	a[low] = a[j];
	a[j] = pivot;
	return j;
    }
}